package org.example.myleet.bitmath;

import org.example.myleet.Utils.Assert;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
import java.util.List;

public class BitmathSolution {

    /**
     * 剑指Offer 15
     * 注意：本题与主站 191 题相同：https://leetcode-cn.com/problems/number-of-1-bits/
     */
    public int hammingWeight(int n) {
        int count = 0;
        for (int i = 0; i < 32; ++i) {
            if ((n & 1) == 1) {
                ++count;
            }
            n >>>= 1;
        }
        return count;
    }

    /**
     * 137【位运算+计数】只出现一次的数字 II
     */
    public int singleNumber137(int[] nums) {
        int[] bitCnt = new int[32];
        for (int num : nums) {
            for (int i = 0; i < 32; ++i) {
                bitCnt[i] += (num >> i) & 1;
            }
        }
        int answer = 0;
        int i = 31;
        for (; i >= 0; --i) {
            if (bitCnt[i] != 0) break;
        }
        for (; i >= 0; --i) {
            answer = (answer << 1) + bitCnt[i] % 3;
        }
        // System.out.println();
        return answer;
    }

    /**
     * 187【位运算】重复的DNA序列
     * 定义A=00，C=01，G=10，T=11
     */
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> result = new ArrayList<>();
        if (s.length() < 10) {
            return result;
        }
        HashMap<Integer, Boolean> memory = new HashMap<>();
        String prime = s.substring(0, 10);
        int bits = string2Bits(prime);
        memory.put(bits, false);
        for (int i = 10; i < s.length(); ++i) {
            char c = s.charAt(i);
            bits = slideNext(bits, c);
            Boolean added = memory.get(bits);
            if (null != added) {
                if (!added) {
                    result.add(bits2String(bits));
                    memory.put(bits, true);
                }
            } else {
                memory.put(bits, false);
            }
        }
        return result;
    }
    private int transfer(char c) {
        int bit;
        switch (c) {
            case 'A': {
                bit = 0;
                break;
            }
            case 'C': {
                bit = 1;
                break;
            }
            case 'G': {
                bit = 2;
                break;
            }
            case 'T': {
                bit = 3;
                break;
            }
            default: bit = 0;
        }
        return bit;
    }
    private char transfer(int bit) {
        char c;
        switch (bit) {
            case 0: {
                c = 'A';
                break;
            }
            case 1: {
                c = 'C';
                break;
            }
            case 2: {
                c = 'G';
                break;
            }
            case 3: {
                c = 'T';
                break;
            }
            default: c = 'A';
        }
        return c;
    }
    private int string2Bits(String s) {
        int i = 0;
        for (char c : s.toCharArray()) {
            int bit = transfer(c);
            i <<= 2;
            i += bit;
        }
        return i;
    }
    private String bits2String(int bits) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 10; ++i) {
            int tail = bits & 0b11;
            sb.append(transfer(tail));
            bits >>= 2;
        }
        return sb.reverse().toString();
    }
    private int slideNext(int bits, char c) {
        int formatter = 0b00000000000011111111111111111111;
        bits <<= 2;
        bits &= formatter;
        bits += transfer(c);
        return bits;
    }

    /**
     * 190【位运算】颠倒二进制位
     * 1 ms
     * 与p191类似
     */
    public int reverseBits(int n) {
        //firstOne - 第一位是否1
        int N = n, firstOne = 0;
        if (n < 0) {
            //首位需要进行取反补码以获得第1位的0或1，然后N剩下的31位可以不断右移获得0或1，叠加到result中实现颠倒
            N = N & 0b01111111111111111111111111111111;
            firstOne = 1;
        }
        int result = 0;
        for (int i=0; i<31; ++i) {
            //x - N的末尾是不是1，x == 1说明末尾是1，否则末尾是0
            int x = N ^ (N-1);
            if (x == 1) {
                //末尾是1时，result+1并左移，相当于叠了一个1
                result += 1;
            }
            result <<= 1;
            //N向右移相当于弹出一位
            N >>>= 1;
        }
        if (firstOne == 1) {
            //最后把符号位的1补上
            ++result;
        }
//        System.out.println(Integer.toBinaryString(result));
        return result;
    }

    /**
     * 191【位运算】位1的个数
     * 1 ms
     */
    public int hammingWeight191(int n) {
        int count = 0, N = n;
        if (n < 0) {
            //JAVA由于使用了第一位作为符号位，因此如果第一位是1时，需要对输入的数字做除符号位以外的反补码处理
            //与0b01111111111111111111111111111111进行与运算使得第一位符号位变成0，后面所有位置保持其0或1的情况，相当于去除了符号位的1，++count
            N = N & 0b01111111111111111111111111111111;
            ++count;
        }
        while (N > 0) {
            //逐位检查末尾是否为0（mod 2 = 0时说明是0，否则就是1），记数，然后整体向右移动1位，直至变成0完全移除所有1
            if (N % 2 > 0) {
                ++count;
            }
            N >>= 1;
        }
        return count;
    }

    /**
     * 260【位运算】只出现一次的数字 III
     * 异或运算的应用：两个相同的数进行异或运算后结果为0，连续进行异或运算时如果中途存在两个相同的数字x，则运算结果中x的异或运算作用会被排除
     */
    public int[] singleNumber(int[] nums) {
        //进行第一次异或运算，最终出现两次的数字全部消失，只剩下x1^x2的结果，因为x1!=x2，因此x1^x2的结果必不为0
        int xorResult = 0;
        for (int num : nums) {
            xorResult ^= num;
        }
        //下面需要一个比较关键的mask，即取xorResult二进制表示中的最后一个1，可以从xorResult最后一位开始往高位搜索
        //mask代表的含义是x1和x2在mask为1的那一位上出现不同
        int mask = 1;
        while ((xorResult & 1) != 1) {
            xorResult >>= 1;
            mask <<= 1;
        }
        //利用mask可以将所有的数字分为两组，其中x1和x2在不同的组中，而且不同的组中除x1或x2以外其他数字必定成对存在，其连续异或运算结果为0
        //剩下的数字即为x1和x2，分别在不同组中
        int[] answer = new int[2];
        for (int num : nums) {
            if ((num & mask) > 0) {
                answer[0] ^= num;
            } else {
                answer[1] ^= num;
            }
        }
        return answer;
    }

    /**
     * 289【原地算法+位运算】生命游戏
     * 规则：
     *     1、如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
     *     2、如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
     *     3、如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
     *     4、如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
     *
     *     这里使用的原地算法规则如下：
     *     0b00=0=初始死，下一回合还是死
     *     0b01=1=初始生，下一回合变死
     *     0b10=2=初始死，下一回合变生
     *     0b11=3=初始生，下一回合还是生
     *     value & 1，即value & 0b01，得到右边一位，代表本回合的状态
     *     value >> 1，即右移1位，得到左边一位，代表下一回合的状态
     */
    public void gameOfLife(int[][] board) {
        //y,x
        int[][] directions = new int[][]{
                {-1,-1}, {-1,0}, {-1,1},
                {0,-1},         {0,1},
                {1,-1}, {1,0}, {1,1}
        };
        int h = board.length;
        int w = board[0].length;
        //第一次遍历board是计算新状态
        for (int y=0; y<h; y++) {
            for (int x=0; x<w; x++) {
                //计算周围活的细胞
                int live = 0;
                for (int[] dir : directions) {
                    int checkY = y + dir[0];
                    int checkX = x + dir[1];
                    if (checkY >= 0 && checkY < h && checkX >= 0 && checkX < w) {
                        //在地图范围内，进行计数
                        if ((board[checkY][checkX] & 1) == 1) {
                            //本回合活的，活+1
                            ++live;
                        }
                    }
                }
                if ((board[y][x] & 1) == 1) {
                    //本回合是活的，按活的规则1,2,3进行
                    if (live < 2) {
                        //规则1，先活后死
                        board[y][x] = 0b01;
                    } else if (live < 4) {
                        //规则2，活还是活
                        board[y][x] = 0b11;
                    } else {
                        //规则3，先活后死
                        board[y][x] = 0b01;
                    }
                } else {
                    //本回合是死的，按规则4进行
                    if (live == 3) {
                        //规则4，先死后活
                        board[y][x] = 0b10;
                    } else {
                        //否则，死还是死
                        board[y][x] = 0b00;
                    }
                }
            }
        }
        //第二次遍历board是刷新board的最新状态
        for (int y=0; y<h; y++) {
            for (int x = 0; x < w; x++) {
                board[y][x] = board[y][x] >> 1;
            }
        }
    }

    /**
     * 318【位运算】最大单词长度乘积
     * 思路：利用位运算进行状态压缩，快速比对两个单词是否存在相同的字母，遍历过程使用暴力O(n^2)
     */
    public int maxProduct(String[] words) {
        int max = 0;
        int n = words.length;
        int[] masks = new int[n];
        for (int i = 0; i < n; ++i) {
            String word = words[i];
            //将一个单词的字母是否出现的结果做成掩码，存储在32位有符号整数中，使用前26位就够用了
            int mask = 1 << (word.charAt(0) - 'a');
            for (int j = 1; j < word.length(); ++j) {
                mask |= (1 << (word.charAt(j) - 'a'));
            }
            masks[i] = mask;
        }
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if ((masks[i] & masks[j]) == 0) {
                    //两个掩码进行与操作，如果结果为0说明对应的两个单词的字母完全不相同
                    max = Math.max(max, words[i].length() * words[j].length());
                }
            }
        }
        return max;
    }

    /**
     * 338【位运算：最高有效位法】比特位计数
     * 1 ms
     * 解释：
     * 可以换一个思路，当计算 i 的「一比特数」时，如果存在 0≤j<i，j 的「一比特数」已知，且 i 和 j 相比，i 的二进制表示只多了一个 1，则可以快速得到 i 的「一比特数」。
     * <p>
     * 令 bits[i] 表示 i 的「一比特数」，则上述关系可以表示成：bits[i]=bits[j]+1。
     * <p>
     * 对于正整数 x，如果可以知道最大的正整数 y，使得 y≤x 且 y 是 2 的整数次幂，则 y 的二进制表示中只有最高位是 1，其余都是 0，此时称 y 为 x 的「最高有效位」。令 z=x−y，显然 0≤z<x，则 bits[x]=bits[z]+1。
     * <p>
     * 为了判断一个正整数是不是 2 的整数次幂，可以利用方法一中提到的按位与运算的性质。如果正整数 y 是 2 的整数次幂，则 y 的二进制表示中只有最高位是 1，其余都是 0，因此 y&(y−1)=0。由此可见，正整数 y 是 2 的整数次幂，当且仅当 y&(y−1)=0。
     * <p>
     * 显然，0 的「一比特数」为 0。使用 highBit 表示当前的最高有效位，遍历从 1 到 num 的每个正整数 i，进行如下操作。
     * <p>
     * 如果 i&(i−1)=0，则令 highBit=i，更新当前的最高有效位。
     * <p>
     * i 比 i−highBit 的「一比特数」多 1，由于是从小到大遍历每个数，因此遍历到 i 时，i−highBit 的「一比特数」已知，令 bits[i]=bits[i−highBit]+1。
     * <p>
     * 最终得到的数组 bits 即为答案。
     * <p>
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/counting-bits/solution/bi-te-wei-ji-shu-by-leetcode-solution-0t1i/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    public int[] countBits(int num) {
        //highBit为最高有效位，即当前i的二进制中最接近i的2的整数次幂，形如100...，只有最高位为1，其余位都为0，只含有一个1
        int n = num + 1, highBit = 0;
        int[] result = new int[n];
        result[0] = 0;
        for (int i = 1; i < n; i++) {
            if ((i & (i - 1)) == 0) {
                //i是2的整数次幂，更新最高有效位，而且只有一个1
                highBit = i;
                result[i] = 1;
            } else {
                //i的1的个数一定是(i-highBit)的1的个数多一个
                result[i] = result[i - highBit] + 1;
            }
        }
        return result;
    }

    /**
     * 342【位运算】4的幂
     * 找规律，4的x次方，其中x = 0,1,2...，则比特位置为1,3,5...
     */
    public boolean isPowerOfFour(int n) {
        if (n < 1) return false;
        //1431655765 = 1010101010101010101010101010101(2)，首先保证n只有1个比特，然后通过&操作保证这一个比特是在所需的1位置上
        return ((n & (n - 1)) == 0) && ((n & 1431655765) == n);
    }

    /**
     * 371【位运算】两个整数的和
     * 官方解答
     * 可以发现，对于整数 a 和 b：
     * 在不考虑进位的情况下，其无进位加法结果为 a⊕b。
     * 而所有需要进位的位为 a&b，进位后的进位结果为 (a&b)<<1。
     */
    public int getSum(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }

    /**
     * 421【贪心+异或运算+哈希表】数组中两个数的最大异或值
     * https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/solutions/9289/li-yong-yi-huo-yun-suan-de-xing-zhi-tan-xin-suan-f/
     * 关键原理：如果有三个数，满足其中两个数的异或值等于另一个值，那么这三个数的顺序可以任意调换
     * 如果 a ^ b = c 成立，那么a ^ c = b 与 b ^ c = a 均成立
     * 要得到一个最大的异或值，最好的结果就是每一位均为1，针对每一位进行利用贪心的思想进行结果为1的可行性分析
     * 从二进制值的左边开始，假设取i位为前缀，贪心假设这一位可以为1（假设为c），如果在所有数字的前缀中（假设为a），找到一个数字的前缀b，使得c ^ a = b，则一定可以找到a ^ b = c，即存在两个数，其异或结果的前i位的前缀为c
     */
    public int findMaximumXOR(int[] nums) {
        //结果，从二进制数左边开始逐位增加
        int res = 0;
        //mask用于产生每个数的前i位前缀，方法就是mask & num
        int mask = 0;
        for (int i = 31; i >= 0; --i) {
            //总共遍历32次，时间复杂度为O(32N)=O(N)
            //假设右边一位可以为1，记这个临时贪心设定的值为res1
            int res1 = res | (1 << i);
            //mask也是向右延长一位
            mask = mask | (1 << i);
            //记录所有数字前缀的集合
            Set<Integer> prefixSet = new HashSet<>();
            for (int num : nums) {
                //利用mask提取每个数的前缀
                prefixSet.add(mask & num);
            }
            for (int prefix : prefixSet) {
                if (prefixSet.contains(res1 ^ prefix)) {
                    //如果存在某个prefix，其res1 ^ prefix是另存在的一个前缀，则一定可以找到两个数的异或值得到这个前缀，因此res的第32-i位一定可以为1
                    res = res1;
                    break;
                }
                //否则如果遍历完所有前缀还是找不到这种结果，说明res第32-i位不能为1，只好为0
            }
        }
        return res;
    }

    //p1763
    public String longestNiceSubstring(String s) {
        int lower = 0, upper = 0;
        char[] charArr = s.toCharArray();
        String result = "";
        int l = 0, r = l;
        while (l < charArr.length) {
            char c = charArr[r];
            if (Character.isUpperCase(c)) {
                upper |= 1 << (c - 'A');
            } else {
                lower |= 1 << (c - 'a');
            }
            if (lower == upper && r - l + 1 > result.length()) {
                char[] ca = new char[r - l + 1];
                System.arraycopy(charArr, l, ca, 0, r - l + 1);
                result = new String(ca);
            }
            ++r;
            while (r >= charArr.length && l < charArr.length) {
                ++l;
                r = l;
                lower = 0;
                upper = 0;
            }
        }
        return result;
    }

    /**
     * 2586【位运算】统计范围内的元音字符串数
     */
    public int vowelStrings(String[] words, int left, int right) {
        //用一个int记录5个元音的出现情况
        int mask = 0;
        mask |= 1; //a-1
        mask |= 1 << 4; //e-5
        mask |= 1 << 8; //i-9
        mask |= 1 << 14; //o-15
        mask |= 1 << 20; //u-21
        int answer = 0;
        for (int i = left; i <= right; ++i) {
            String word = words[i];
            //如果第一个字母和最后一个字母在二进制上代表的位置和mask中的1的位置有对应的，则算作一个符合的word
            if ((mask & (1 << (word.charAt(0) - 'a'))) > 0 && (mask & (1 << (word.charAt(word.length() - 1) - 'a'))) > 0) ++answer;
        }
        return answer;
    }

    /**
     * 2680[贪心思想+位运算+前缀和思想]最大或值
     */
    public long maximumOr(int[] nums, int k) {
        int n = nums.length;
        //计算前缀或运算和后缀或运算的结果，则每一个数字单独拎出来时，最终整体或运算结果都可以视作prefix[i] | nums[i] | suffix[i+1]
        int[] prefix = new int[n + 1];
        int[] suffix = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            prefix[i + 1] = prefix[i] | nums[i];
            suffix[n - i - 1] = suffix[n - i] | nums[n - i - 1];
        }
        long answer = 0L;
        for (int i = 0; i < n; ++i) {
            //贪心思想：左移操作全部给到一次数字上肯定是最优的，反证：如果其中的一些左移操作分给其他数字，则最左边的1位置肯定不够全部操作一个数字的那么左
            answer = Math.max(answer, prefix[i] | ((long) nums[i] << k) | suffix[i + 1]);
        }
        return answer;
    }

    /**
     * 2859【位运算+分治】计算 K 置位下标对应元素的和
     * 本题关键是巧妙利用位运算和分治的思想实现每一步完成一半位置的运算（时间复杂度log2(C)，C为数字的位数），而不用循环地运算（时间复杂度C）
     * 将某个数x（10位二进制数）看成(abcdefghij)2，在编写代码时，我们需要使用位运算。三步操作分别对应着：
     * 1、通过 x & 0101010101 得到 (0b0d0f0h0j)2，以及 (x & 1010101010) >> 1 得到 (0a0c0e0g0i)2，将两个数加在一起，前两位就是ab相加的结果，只会是这3种情况：00、01、10，其余的cd、ef、gh、ij位置相加也是一样的，这时候其实是分治法的倒数第二层（倒数第一层其实是精确到每一位，此时不用相加已知道每一位的结果）就是将上一层分治的结果合并在一起，精确到一位一位相加。
     * 2、通过 x & 1100110011 得到 (ab00ef00ij)2，以及(x & 0011001100) >> 2 得到 (00cd00gh)2，将两个数加在一起，前两位还是ab的结果，第3~6位是cd+ef的结果，7~10位是gh+ij的结果，这里是分治法的倒数第三层，也是将上一层分治的结果合并在一起，精确到两位两位相加。
     * 3、通过 x >> 8 得到 (ab)2，以及 (x >> 4) & 1111 得到 (cdef)2，以及 x & 1111 (ghij)2，这三个结果加在一起（最后一步合并）就是总的二进制数位为1的数量。
     * 作者：力扣官方题解
     * 链接：https://leetcode.cn/problems/sum-of-values-at-indices-with-k-set-bits/solutions/2614602/ji-suan-k-zhi-wei-xia-biao-dui-ying-yuan-axzr/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    public int sumIndicesWithKSetBits(List<Integer> nums, int k) {
        int sum = 0;
        for (int i = 0; i < nums.size(); ++i) {
            int x = ((i & 0b1010101010) >> 1) + (i & 0b0101010101);
            x = (x & 0b1100110011) + ((x & 0b0011001100) >> 2);
            x = (x >> 8) + ((x >> 4) & 0b1111) + (x & 0b1111);
            if (x == k) sum += nums.get(i);
        }
        return sum;
    }

    /**
     * 3097【滑动窗口+位运算】或值至少为 K 的最短子数组 II
     */
    private void helper3097_addNum(int num, int[] bitCnt) {
        for (int i = 0; i < bitCnt.length; ++i) {
            bitCnt[i] += (num >> i) & 1;
        }
    }
    private void helper3097_rmNum(int num, int[] bitCnt) {
        for (int i = 0; i < bitCnt.length; ++i) {
            bitCnt[i] -= (num >> i) & 1;
        }
    }
    private int helper3097_calRe(int[] bitCnt) {
        int re = 0;
        for (int i = 0; i < bitCnt.length; ++i) {
            if (bitCnt[i] > 0) {
                re |= 1 << i;
            }
        }
        return re;
    }
    public int minimumSubarrayLength(int[] nums, int k) {
        if (k == 0) return 1;
        int n = nums.length, l = 0, r = 0, answer = Integer.MAX_VALUE, re = 0;
        int[] bitCnt = new int[30];
        while (true) {
            //滑动窗口法+位运算法，逐步延伸窗口右侧直至找到窗口子数组或运算>=k的情况，再缩小左侧以找到一个最小的子数组
            if (re >= k) {
                answer = Math.min(answer, r - l);
                //移除窗口左侧元素
                helper3097_rmNum(nums[l], bitCnt);
                re = helper3097_calRe(bitCnt);
                ++l;
            } else {
                if (r >= n) break;
                //加入窗口右侧元素
                helper3097_addNum(nums[r], bitCnt);
                re = helper3097_calRe(bitCnt);
                ++r;
            }
        }
        return answer == Integer.MAX_VALUE ? -1 : answer;
    }

    public static void main(String[] args) {
        BitmathSolution solution = new BitmathSolution();
        Assert.isTrue(30 == solution.maximumOr(new int[]{12,9}, 1));
//        Assert.isTrue(3 == solution.minimumSubarrayLength(new int[]{2,1,8}, 10));
//        Assert.isTrue(1 == solution.minimumSubarrayLength(new int[]{1,2,3}, 2));
    }
}
